#ifndef UNIONFIND_H
#define	UNIONFIND_H

#include <exception>

class UnionFindException : public std::exception{};

class InvlidIdException : public UnionFindException{};
class InexistentSetException : public UnionFindException{};

class UnionFind {
	static const int INVALID_VALUE = -1;

	struct Set {
		bool doesExist;
		int size;
		int forestIndex;

		// Default C'tor just for temporary use when creating sets array.
		Set() : doesExist(false), 
			size(INVALID_VALUE),
			forestIndex(INVALID_VALUE) {}

		Set(int forestIndex) : doesExist(true),
			size(1),
			forestIndex(forestIndex) {}
	};
	class Member {
		int parentIndex;
		int setIndex;

	public:
		// Default C'tor just for temporary use when creating forest array.
		Member() : parentIndex(INVALID_VALUE), setIndex(INVALID_VALUE) {}
		
		void setParent(int parentIndex) {
			this->parentIndex = parentIndex;
			setIndex = INVALID_VALUE;
		}
		
		void setSet(int setIndex) {
			this->setIndex = setIndex;
			parentIndex = INVALID_VALUE;
		}

		int getParent() { return parentIndex; }
		int getSet() { return setIndex; }
	};

	int n;
	Set* sets;
	Member* forest;

	bool isLegalId(int id);

public:
	UnionFind(int n);
	~UnionFind();
	bool isSet(int setId);
	void unite(int targetSet, int otherSet);
	int find(int memberId);
};

#endif	/* UNIONFIND_H */

